package vip.zhenzicheng.algorithm.leetcode.binary_tree;

import vip.zhenzicheng.algorithm.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * <a href="https://leetcode.cn/problems/binary-tree-right-side-view/">二叉树的右视图 [中等]</a>
 *
 * @author zhenzicheng
 * @date 2022-06-29 14:52
 */
public class BinaryTreeRightSideView_199 {

  public List<Integer> rightSideView(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    rightView(root, result, 0);
    return result;
  }

  public void rightView(TreeNode root, List<Integer> result, int depth) {
    if (root == null) {
      return;
    }

    // 深度相同代表找到所需节点，对于右子树遇到右子树节点保存，对于左子树，只有不存在右子树的节点才会加入结果集
    if (depth == result.size()) {
      result.add(root.val);
    }
    // 找下一层，优先找右子树
    rightView(root.right, result, depth + 1);
    rightView(root.left, result, depth + 1);
  }
}
